package hot;

public class Num84 {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        int n = heights.length;
        int[] left_i = new int[n];
        int[] right_i = new int[n];
        left_i[0] = -1;
        right_i[n - 1] = n;
        for(int i = 1; i < n; i++) {
            int temp = i - 1;
            while(temp >= 0 && heights[temp] >= heights[i]) temp = left_i[temp];
            left_i[i] = temp;
        }
        for(int i = n - 2; i >= 0; i--) {
            int temp = i + 1;
            while(temp < n && heights[temp] >= heights[i]) temp = right_i[temp];
            right_i[i] = temp;
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            ans = Math.max(ans,(right_i[i] - left_i[i] - 1) * heights[i]);
        }
        return ans;
    }
}
